package interview.ncolors;

public class NColors {
	public int run(int[] chain, int n) {
		int[] colors = new int[n];
		for(int i = 0; i < n; i++) {
			colors[i] = 0;
		}
		
		int winLeft, winRight;
		winLeft = 0; winRight = 0;
		int minLen = 0, minStart = 0;;
		boolean done = false;
		int length = chain.length;
		while(!done) {
			colors[chain[winRight] - 1]++;
			if(allColorsFound(colors)) {
				while(winLeft != winRight) {
					colors[chain[winLeft] - 1]--;
					winLeft = (winLeft + 1) % length;
					if(winLeft == 0) {
						done = true;
						break;
					}
					if(!allColorsFound(colors)) {
						int newLen;
						if(winLeft < winRight) {
							newLen = winRight - winLeft + 2;
						} else {
							newLen = winRight + n - winLeft + 2;
						}
						if(minLen == 0 || newLen < minLen) {
							minLen = newLen;
							minStart = winLeft - 1;
						}
						break;
					} 
				}
			} else {
				winRight = (winRight + 1) % length;
			}
		}
		return minStart;
	}

	private boolean allColorsFound(int[] colors) {
		for(int i = 0; i < colors.length; i++) {
			if(colors[i] == 0) {
				return false;
			}
		}
		return true;
	}
}
